在學會了 Pointer 的技巧後，今天來介紹 Sliding Window
基本上 Sliding Window 可視為一種廣義的 Pointer

但Pointer注重於兩端位置指的值，而Sliding Window則是注重整個 window/range 範圍內的所有元素

What is Sliding Window

• Sliding Window is an slogrithmic approach that involves iterating over a collection of items(array) with a fixed-size window, where the window slides from left to right.
• The Sliding Window technique focuses on analyzing all the elements within a defined window or range, while the Two Pointer technique typically focuses on the value at the two pointer positions.

簡短來說就是 Sliding Window 這個技巧，會在 dataset 中建立 subsets/window elements（固定size / 不固定size），在 dataset 中不斷滑/移動，藉此進行 subsets 內的運算（ex:取總和、找到最多不重複字符等等）

圖片來源

圖片來源

When to use Sliding Window technique?

• You need to examine all consecutive subsets of a dataset(string/array) in a way that avoids repetitive recalculations.
• You want to check if these subsets meet certain conditions(e.g. sums, maxium length, uniqueness)

哪些場合適合 Sliding Window？

• 需要避免重複進行計算的方法去檢查 dataset 內的子集合(subset)
• 需要檢查子集合(subset)是否符合某些條件(加總/最大長度/不重複性)

Calculate the max sum / min sum of consecutive elements in an array 計算連續N個元素於陣列的最大/最小總和

Exercise:Get the minimize sum of window

這裡說明一下為何 for loop i 到小於等於 array.length - windowSize
因為最後一位為 array.length-1
從最後一位倒退到 array-windowSize 剛好就是 last window 的開頭，所以用 <= 而非 <

function getMinValue(arr, windowSize) {
     let min_value = Infinity;
     let result = [];
     // exclude the condition that the window is larger than dataset
     if (windowSize > arr.length) {
         console.error("window size can not larger than length of dataset");
         return false;
     }

     for (let i = 0; i <= arr.length - windowSize; i++) {
         let sum = arr.slice(i, i + size).reduce((a, b) => a + b);
         if (sum < min_value) {
             min_value = sum;
             result = [...arr.slice(i, i + size)];
         }
      }
      return min_value;
}

getMinValue([2, 7, 3, 0, 6, 1, -5, -12, -11], 3); // return -28

但其實這個做法仍有改進的空間..容我先賣個關子XD

相關資源

How to Use the Sliding Window Technique – Algorithm Example and Solution
https://www.freecodecamp.org/news/sliding-window-technique/
The Sliding Window Technique: A Powerful Algorithm for JavaScript Developers
https://dev.to/sanukhandev/the-sliding-window-technique-a-powerful-algorithm-for-javascript-developers-3nfm
window sliding technique
https://www.geeksforgeeks.org/window-sliding-technique/